import random


# Question 1
# Fonction graph_nim
def graphe_nim(n,g,j):
    # Clé du dictionnaire (joueur courant j)
    cle_joueur_courant = str(n) + '-J' + str(j)

    # Si la clé n'existe pas, on la crée
    if cle_joueur_courant not in g:
        g[cle_joueur_courant] = set()

    # Pour chaque cas :
    # Enlever 1,2 ou 3 allumettes
    for i in [1,2,3]:
        # Si on peut enlever i allumettes des n restantes
        if (n-i) > 0 :
            # Nouvelle clé avec (n-i) allumettes restantes
            # pour l'autre joueur (1-j)
            cle_autre_joueur = str(n-i) + '-J' + str(1-j)

            # Si la nouvelle clé n'existe pas, créé l'ensemble vide
            if cle_autre_joueur not in g:
                g[cle_autre_joueur] = set()

            # Ajoute le nouvel état (cle_autre_joueur)
            # au joueur courant
            if cle_autre_joueur not in g[cle_joueur_courant]:
                g[cle_joueur_courant].add(cle_autre_joueur)

            # Appel récursif avec changement de joueur
            g = graphe_nim(n-i,g,1-j)

    return g

# Test question 1
# Dictionnaire du graphe vide
g= {}
print(graphe_nim(4,g,0))

# Question 2 : Sommets contrôlés par le joueur j
def Sommets_Joueur(j,g):
    sommets = []
    for cle in g:
        if 'J'+str(j) in cle:
            sommets.append(cle)
    return sommets

# Test Question 2
print("\nSommets controlés par J0")
print(Sommets_Joueur(0,g))


# Question 3
# F0 = {'1-J1'} : c'est le seul état sans issue où c'est à J1 de jouer,
# le forçant à prendre la dernière allumette


# Question 4
# On trouve : C0 = {('4-J0','1-J1'),('4-J0','3-J1','2-J0','1-J1')}


# Question 5 : Calcul des degrés sortants
def degres_sortants(g):
    return {s:len(g[s]) for s in g}

# Test de la question 5
print("\nCalcul des degrés sortants")
deg = degres_sortants(g)
print(deg)

# Question 6 : Calcul des sommets cibles de Ji
def sommets_cibles(g,i):
    Fi = []

    # Calcul des sommets contrôlés par l'adversaire
    S1_i = Sommets_Joueur(1-i,g)

    # Construction de l'ensemble Fi
    deg = degres_sortants(g)
    for s in S1_i:
        if deg[s] == 0:
            Fi.append(s)

    return Fi

# Test question 6
print("\nCalcul des sommets cibles pour J0")
print(sommets_cibles(g,0))


# Question 7:
# Omega0 = {'1-J1'}
# Omega1 = {'1-J1','4-J0','2-J0'}
# Omega2 = {'1-J1','4-J0','2-J0'} = Omega car stationnaire

# Question 8
# La position '4-J0' appartient à l’attracteur, donc c’est une
# position gagnante pour J0 et donc J0 possède une stratégie gagnante.


# Question 9 : Calcul des prédécesseurs
def predecesseurs(g):
    pred = {s:[] for s in g}

    for s in g:
        for t in g[s]:
            pred[t].append(s)
    return pred

# Test  question 9
print("\nConstruction des prédécesseurs")
pred = predecesseurs(g)
print(pred)

# Question 10 : Traitement des sommets / mise à jour de l'attracteur
def traiter_sommet(s,pred,deg,Si,omega,file):
    # Pour chaque prédécesseur du sommet s
    for p in pred[s]:
        # Test si p est déjà dans omega ou non
        if p not in omega:
            # Si p n'est pas dans omega, regarde si p est controlé par Ji
            if p in Si:
                # Si p est controlé par Ji, alors on l'ajoute à l'attracteur
                # et à la file
                omega.append(p)
                file.append(p)
            else:
                # Sinon, on décrémente son compteur
                deg[p] = deg[p] - 1
                # Et on vérifie si il est nul
                if deg[p] == 0:
                    # Si le compteur est nul, on ajoute p à l'attracteur
                    # et à la file
                    omega.append(p)
                    file.append(p)

    return omega,file

# Question 11 : Algorithme de l'attracteur
def Attracteur(g,Si,F):
    # Initialise l'attracteur et la file avec les sommets de la cible F
    omega = [f for f in F]
    file = [f for f in F]

    # Initialisation des prédécesseurs des sommets du graphe
    pred = predecesseurs(g)

    # Calcul des degrés sortants des sommets du graphe
    deg = degres_sortants(g)


    while len(file) !=0:
        # Récupère le sommet à traiter dans la file
        s = file.pop(0)

        # Traitement du sommet s
        omega, file = traiter_sommet(s,pred,deg,Si,omega,file)

    return omega

# Test  question 11
print("\nCalcul de l'attracteur de F0 pour le joueur J0")
g = graphe_nim(4,{},0)
F0 = sommets_cibles(g,0)
S0 = Sommets_Joueur(0,g)
Omega0 = Attracteur(g,S0,F0)
print(Omega0)

# Question 12 : Test pour plusieurs valeurs de n
# Calcul des attracteurs de F0 pour le joueur J0 (n=1..11)
# []
# ['1-J1', '2-J0']
# ['1-J1', '3-J0']
# ['1-J1', '4-J0', '2-J0']
# ['1-J1', '3-J0', '2-J0']
# ['1-J1', '4-J0', '2-J0', '3-J0', '5-J1', '6-J0']
# ['1-J1', '3-J0', '2-J0', '4-J0', '5-J1', '7-J0']
# ['1-J1', '4-J0', '2-J0', '3-J0', '5-J1', '8-J0', '6-J0']
# ['1-J1', '3-J0', '2-J0', '4-J0', '5-J1', '7-J0', '6-J0']
# ['1-J1', '4-J0', '2-J0', '3-J0', '5-J1', '8-J0', '6-J0', '7-J0', '9-J1', '10-J0']
# ['1-J1', '3-J0', '2-J0', '4-J0', '5-J1', '7-J0', '6-J0', '8-J0', '9-J1', '11-J0']

# => J0 possède une stratégie gagnante depuis n-J0
#    si et seulement si n ≢ 1 (mod 4).
print("\nCalcul des attracteurs de F0 pour le joueur J0 (n=1..11)")
for n in range(1,12):
    g = graphe_nim(n,{},0)
    F0 = sommets_cibles(g,0)
    S0 = Sommets_Joueur(0,g)
    print(Attracteur(g,S0,F0))


# Question 13 : fonction d'évaluation des feuilles
def f_nim(feuille,i):
    # Récupère le joueur
    joueur = feuille.split("-")[1]

    # Si c'est le joueur Ji, retourne -1
    if joueur == 'J'+str(i):
        return -1

    # Sinon, retourne +1
    else:
        return 1


# Test question 13
print("\nFonction d'évaluation")
g = graphe_nim(4,{},0)
F0 = sommets_cibles(g,0)
S0 = Sommets_Joueur(0,g)
Omega0 = Attracteur(g,S0,F0)

print("J1 sur '1-J1': ",f_nim('1-J1',1))
print("J0 sur '1-J1': ",f_nim('1-J1',0))
print("J1 sur '1-J0': ",f_nim('1-J0',1))
print("J0 sur '1-J0': ",f_nim('1-J0',0))

# Question 14 : Algorithme Minimax
def MINIMAX(g,i,f,s):
    # Si s est une feuille, retourne sa valeur
    if g[s] == set():
        return f(s,i)

    # Si c'est au joueur Ji de jouer, retourne le MAX
    if s in Sommets_Joueur(i,g):
        vmax = float('-inf')
        for succ in g[s]:
            vmax = max(vmax,MINIMAX(g,i,f,succ))
        return vmax

    # Sinon, c'est à l'adversaire de jouer. Reoturne le MIN
    else:
        vmin = float('inf')
        for succ in g[s]:
            vmin = min(vmin,MINIMAX(g,i,f,succ))
        return vmin

# Test question 14
print("\nFonction MINIMAX")
g = graphe_nim(4,{},0)
print("MINIMAX sur '1-J1:", MINIMAX(g,0,f_nim,'1-J1'))
print("MINIMAX sur '2-J0:", MINIMAX(g,0,f_nim,'2-J0'))
print("MINIMAX sur '1-J0:", MINIMAX(g,0,f_nim,'1-J0'))
print("MINIMAX sur '3-J1:", MINIMAX(g,0,f_nim,'3-J1'))
print("MINIMAX sur '2-J1:", MINIMAX(g,0,f_nim,'2-J1'))
print("MINIMAX sur '4-J0:", MINIMAX(g,0,f_nim,'4-J0'))

# Question 15 : MINIMAX(g,0,f_nim,'4-J0') renvoie +1
#               ce qui signifie que J0 possède une
#               stratégie gagnante

# Question 16 : Voir question 12 + essais avec MINIMAX()

# Question 17 : MINIMAX avec renvoie du meilleur coup
def strategie_minimax(g,i,f,s):
    # meilleur_coup
    meilleur_coup = None

    # Si s est une feuille, retourne sa valeur
    if g[s] == set():
        return f(s,i),meilleur_coup

    # Si c'est au joueur Ji de jouer, retourne le MAX
    if s in Sommets_Joueur(i,g):
        vmax = -1
        for succ in g[s]:
            val = max(vmax,MINIMAX(g,i,f,succ))
            if val > vmax:
                vmax = val
                meilleur_coup = succ
        return vmax,meilleur_coup

    # Sinon, c'est à l'adversaire de jouer. Reoturne le MIN
    else:
        vmin = 1
        for succ in g[s]:
            val = min(vmin,MINIMAX(g,i,f,succ))
            if val < vmin:
                vmin = val
                meilleur_coup = succ
        return vmin,meilleur_coup

# Test question 17
print("\nFonction strategie_minimax")
g = graphe_nim(4,{},0)
print("MINIMAX sur '4-J0:", strategie_minimax(g,0,f_nim,'4-J0'))
g = graphe_nim(5,{},0)
print("MINIMAX sur '5-J0:", strategie_minimax(g,0,f_nim,'5-J0'))
g = graphe_nim(6,{},0)
print("MINIMAX sur '6-J0:", strategie_minimax(g,0,f_nim,'6-J0'))


# Question 18 : Partie simulée
n=6
print("\nSimulation pour n="+str(n))
g = graphe_nim(n,{},0)
s = str(n) + '-J0'
i = 0
###################
while s not in sommets_cibles(g,0) and s not in sommets_cibles(g,1):
    val, coup_ji = strategie_minimax(g,i,f_nim,s)
    if coup_ji == None:
        coup_ji = list(g[s])[random.randint(0,len(g[s])-1)]
    print(s + " -> " + coup_ji)
    i= 1-i
    s = coup_ji